package algorithm_demo.leetcode;

/**
 * 2. 两数相加
 * <a href="https://leetcode.cn/problems/add-two-numbers/"></a>
 * @author Api
 * @date 2023/4/5 22:14
 */
public class Problem_0002_AddTwoNumbers {
    /*
     * 给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     * 示例 1：
     * 输入：l1 = [2,4,3], l2 = [5,6,4]
     * 输出：[7,0,8]
     * 解释：342 + 465 = 807.
     * 示例 2：
     * 输入：l1 = [0], l2 = [0]
     * 输出：[0]
     * 示例 3：
     * 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
     * 输出：[8,9,9,9,0,0,0,1]
     * */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(2);
        listNode1.next = new ListNode(4);
        listNode1.next.next = new ListNode(3);

        ListNode listNode2 = new ListNode(5);
        listNode2.next = new ListNode(6);
        listNode2.next.next = new ListNode(9);
        listNode2.next.next.next = new ListNode(9);
        ListNode result = addTwoNumbers(listNode1, listNode2);
        while(result != null){
            System.out.print(result.val+" ");
            result = result.next;
        }
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int len1 = getLength(l1);
        int len2 = getLength(l2);
        ListNode listNode1 = len1>=len2? l1:l2;
        ListNode listNode2 = listNode1 == l1? l2:l1;
        //引用传递
        ListNode curL = listNode1;
        ListNode curS = listNode2;
        //进位信息0
        int carry = 0;
        ListNode last = curL;
        int curNum = 0;
        //先遍历短链表
        while(curS != null){
            curNum = curL.val + curS.val + carry;
            curL.val = curNum % 10;
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
            curS = curS.next;
        }

        while(curL != null){
            curNum = curL.val + carry;
            curL.val = curNum % 10;
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
        }
        //last其实就是为了记录最后一次的链表引用的值，专门针对carry>0的场景
        if (carry != 0){
            //last的引用和curL的引用是相同的，也就是last的下一个值赋值给listNode1
            last.next = new ListNode(1);
        }
        return listNode1;
    }
    /*获取链表的长度*/
    public static int getLength(ListNode head){
        int len = 0;
        while(head != null){
            len++;
            head = head.next;
        }
        return len;
    }
}
